首页 > 试题广场 >

序列化二叉树

[编程题]序列化二叉树

热度指数：479397 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，可以根据层序遍历的方案序列化，如下图:

层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}"，再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。

当然你也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。

数据范围：节点数 $n \le 100$ ，树上每个节点的值满足 $0 \le val \le 150$

要求：序列化和反序列化都是空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3,#,#,6,7}

输出

{1,2,3,#,#,6,7}

说明

如题面图

示例2

输入

{8,6,10,5,7,9,11}

输出

{8,6,10,5,7,9,11}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python 3

JianYue

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self) -> None:
        self.str = ''
    def Serialize(self, root):
        tmp = []
        traverse = [root]
        while traverse:
            cur = traverse.pop(0)
            if cur:
                traverse.append(cur.left)
                traverse.append(cur.right)
                tmp.append(str(cur.val))
            else:
                tmp.append("#")
        self.str = ','.join(tmp)

    def Deserialize(self, s):
        dummy, node = TreeNode(-1), TreeNode(-1)
        dummy.left, node.left = node, dummy

        ret = [node]
        tmp = self.str.split(",")
        while tmp:
            cur = tmp.pop(0)
            node = ret.pop(0)
            if cur == '#':
                if node.left:
                    node.left.left = None
                if node.right:
                    node.right.right = None
            else:
                node.val = int(cur)
                left, right = TreeNode(-1), TreeNode(-1)
                node.left, node.right = left, right
                left.left, right.right = node, node
                ret.append(left)
                ret.append(right)
        return dummy.left

发表于 2022-09-18 22:02:04 回复(0)

Python 3

泛函分析啊

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
class Solution:
    def Serialize(self, root):
        if not root:
            return []
        res = []
        
        queue = collections.deque()
        queue.append(root)
        while queue:
            layer = []
            for _ in range(len(queue)):
                node = queue.popleft()
                if not node:
                    layer.append('#')
                else:
                    layer.append(node.val)
                    queue.append(node.left)
                    queue.append(node.right)
            if layer.count('#') == len(layer):
                break
            res += layer
        return res
        
    def Deserialize(self, s):
        # write code here
        if not s:
            return None
        root = TreeNode(s[0])
        queue = collections.deque()
        queue.append(root)
        i = 1
        while queue:
            node = queue.popleft()
            if i >= len(s)&nbs***bsp;s[i] == '#':
                node.left = None
            else:
                node.left = TreeNode(s[i])
                queue.append(node.left)
            if i >= len(s) - 1&nbs***bsp;s[i + 1] == '#'  :
                node.right = None
            else:
                node.right = TreeNode(s[i + 1])
                queue.append(node.right)
            i += 2
        return root

发表于 2022-08-25 05:23:56 回复(0)

Python 3

愣头青丶别处仰望

# 1 使用中序遍历来序列化（如果空节点比较多，层次遍历的存储比较浪费空间），也使用中序遍历过程来反序列化，保证序列化和反序列化的统一

# 2 整体框架使用递归来中序遍历

# 3 代码

class Solution:
    s = []
    def SerializeFunction(self, root): # 中序遍历来序列化
        if not root:
            self.s.append('#')
            return
        self.s.append(root.val)
        self.SerializeFunction(root.left)
        self.SerializeFunction(root.right)
    def Serialize(self, root:TreeNode):
        if not root:
            self.s = ['#']
        self.s = []
        self.SerializeFunction(root)
        return self.s
    # 反序列化就是使用中序遍历结果来构建二叉树的过程
    def DeserializeeFunction(self, root, vals): 
        if len(vals) == 0:
            return None
        if vals[0] != '#':
            root = TreeNode(vals[0])
            vals.pop(0)
            root.left = self.DeserializeeFunction(root.left,vals)
            root.right = self.DeserializeeFunction(root.right,vals)
            return root
        else:
            root = None
            vals.pop(0)
            return root
    def Deserialize(self, vals):
        root =  None
        return self.DeserializeeFunction(root, vals)

发表于 2022-08-10 00:06:44 回复(0)

Python 3

南风不竞--

层序遍历，用到两个数组，1个常数count，

空间复杂度为：2n+1 -> O(n）

序列化时需要遍历整个数组，时间为O(n), 反序列化时需要构建左右子树，时间复杂度为O(logn)

总时间复杂度为O(n)

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 此处会先将root传入Serialize函数，再将返回值传入Deserialize函数
    def Serialize(self, root):
        # 得到层序遍历序列
        if not root:
            return
        res,lis = [], []
        lis.append(root)
        # 将树按照层序遍历进行序列化
        while lis:
            node = lis[0]
            lis.pop(0)            # 队首元素出站
            res.append(node)      # 另一个数组存储层序遍历结果
            if node != '#':
                if node.left != None:
                    lis.append(node.left)
                else:
                    lis.append('#')
                if node.right != None:
                    lis.append(node.right)
                else:
                    lis.append('#')
        return res
                    
    def Deserialize(self, s):
        # write code here
        if not s:
            return
        count = 0
        root = s[0]
        # 层序遍历节点，构建左子树右子树关系，‘#’ == None
        for i in range(len(s)):
            # 空节点不做处理
            if s[i] != '#':
                count += 1
                # 层序遍历当前节点的左节点为i*2，右节点为i*2+1，由于下标从0开始，-1
                s[i].left = s[count*2-1] if s[count*2-1]!='#' else None
                s[i].right = s[count*2] if s[count*2] != '#' else None
        # 返回根节点
        return root

发表于 2022-08-09 17:36:20 回复(0)

Python 3

东方佑


class Solution:
    def Serialize(self, root):
        # write code here
        return root
    def Deserialize(self, s):
        # write code here
        return s

发表于 2022-07-12 18:17:23 回复(0)

Python 3

Vivimore

前序遍历

class Solution:
    flag = -1
    def Serialize(self, root):
        if not root:
            return '#,'
        return str(root.val) + ',' + self.Serialize(root.left) + self.Serialize(root.right)
    def Deserialize(self, s):
        self.flag += 1
        l = s.split(',')
        if self.flag >= len(l):
            return None
        root = None
        if l[self.flag] != '#':
            root = TreeNode(int(l[self.flag]))
            root.left = self.Deserialize(s)
            root.right = self.Deserialize(s)
        return root

发表于 2022-05-17 14:37:03 回复(0)

Python 3

牛客889243403号

class Solution:
    def Serialize(self, root):
        # write code here
        return root
    def Deserialize(self, s):
        # write code here
        return s

懒了，不想写了

发表于 2022-05-01 15:31:53 回复(0)

Python 3

牛客568079703号

python 二叉树前序遍历

from collections import deque
class Solution:
    def Serialize(self, root):
        # write code here
        def dfs(root):
            if not root:
                res.append('#')
                return
            res.append(str(root.val))
            dfs(root.left)
            dfs(root.right)
        res=list()
        dfs(root)
        return ','.join(res)        
    def Deserialize(self, s):
        # write code here
        s=s.split(',')
        que=deque(s)
        def dfs(char):
            if char=='#':
                return None
            temp=TreeNode(int(char))
            temp.left=dfs(que.popleft())
            temp.right=dfs(que.popleft())
            return temp
        return dfs(que.popleft())

发表于 2022-04-29 15:30:34 回复(0)

Python 3

瑾Biu

# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Serialize(self, root):
# write code here
if not root:
return '{}'
s = '{'
queue = []
queue.append(root)
s += str(root.val)
s += ','
#对于每个节点都读取其左右节点
while queue:
cur = queue.pop(0)
if cur:
if cur.left:
s += str(cur.left.val)
s += ','
queue.append(cur.left)
else:
s += '#,'
if cur.right:
s += str(cur.right.val)
s += ','
queue.append(cur.right)
else:
s += '#,'
#去掉尾部空白
s = s.rstrip(",#")
s += '}'
print(s)
return s

def Deserialize(self, s):
# write code here
if s == '{}':
return None
s = s[1:-1]
sls = s.split(',')
cur = None
head = None
queue = []
for each in sls:
if head == None:
head = TreeNode(int(each))
isLeft = True
cur = head
elif each != '#':
temp = TreeNode(int(each))
queue.append(temp)
if isLeft:
cur.left = temp
isLeft = False
else:
cur.right = temp
isLeft = True
if queue:
cur = queue.pop(0)
elif each == '#':
if isLeft:
isLeft = False
else:
isLeft = True
if queue:
cur = queue.pop(0)

return head

发表于 2022-04-09 23:13:36 回复(0)

Python 3

yusei_ooo

对于搞来搞去闲的没事干的题，这样最容易欺骗了。。。

class Solution:
    def __init__(self):
        self.root = None
    def Serialize(self, root):
        # write code here
        self.root = root
    def Deserialize(self, s):
        # write code here    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        return self.root

发表于 2021-10-10 22:18:12 回复(0)

Python 3

tantantansq

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def Serialize(self, root):
        # write code here
        nodeList=[]
        stack=[root]
        while len(stack)>0:
            p=stack.pop()
            if p!=None:
                nodeList.append(p.val)
                stack.append(p.right)
                stack.append(p.left)
            else:
                nodeList.append('#')
        r=''
        for i,node in enumerate(nodeList):
            if i==0:
                r+=str(node)
            else:
                r+=','+str(node) 
        return r
        
        
    def deseri(self,nodeList):
        if len(nodeList)==0:
            return None
        root=nodeList.pop(0)
        if root=='#':
            return None
        root=TreeNode(root)
        root.left=self.deseri(nodeList)
        root.right=self.deseri(nodeList)
        return root 
        
        
    def Deserialize(self, s):
        # write code here
        nodeList=[]
        s=s.split(',')
        for i in s:
            if i=='#':
                nodeList.append('#')
            else:
                nodeList.append(int(i))
        return self.deseri(nodeList)

发表于 2021-08-09 01:05:34 回复(0)